package ch04;

import edu.princeton.cs.algs4.In;

import java.util.Iterator;
import java.util.Stack;
//DFS
public class DepthFirstPaths {
    private boolean[] marked;
    private int count;
    private final int s;
    private int pathTo[];

    public DepthFirstPaths(Graph graph, int v) {
        this.s = v;
        this.marked = new boolean[graph.V()];
        pathTo = new int[graph.V()];
        DFS(graph,v);
    }

    public void DFS(Graph graph, int v) {

        marked[v] = true;
        count++;
        for (Integer w : graph.adj(v)) {
            pathTo[w] = v;
            if(!marked[w])
                DFS(graph, w);

        }
    }

    public boolean marked(int v) {
        return marked[v];
    }
    public int count(){
        return count;
    }

    public Stack<Integer> pathTo(int v){
        if (!marked[v]) {
            return null;
        }
        Stack<Integer> stack = new Stack<>();
        for (int t = v; t != s; t = pathTo[t]) {
            stack.push(t);
        }
        stack.push(s);
        return stack;
    }


    public static void main(String[] args) {
        Graph graph = Graph.getGraphUseCase();
        DepthFirstPaths dfs = new DepthFirstPaths(graph, 1);
        System.out.println(dfs.marked(1));
        System.out.println(dfs.marked(2));
        System.out.println(dfs.marked(3));
        System.out.println(dfs.marked(4));
        System.out.println(dfs.marked(5));

        Stack<Integer> stack = dfs.pathTo(4);
        while (!stack.isEmpty()) {
            System.out.println(stack.pop());
        }
    }
}
